package com.singzi.algorithm;

import java.util.HashMap;

public class RabinKarp {

    public int rabinKarp(String s1, String s2, int system, int priNumber){


        int length1 = s1.length();
        int length2 = s2.length();
        int h = 1;
        int val1 = 0;
        int val2 = 0;
        for (int i = 0; i < length2-1; i++) {
            h = (h*system) % priNumber;
        }
        for (int i = 0; i < length2; i++) {
            val1 = (system*val1+s1.charAt(i))%priNumber;
            val2 = (system*val2+s2.charAt(i))%priNumber;
        }
        for (int i = 0; i <= length1-length2; i++) {
            if(val1 == val2){
                int j;
                for(j = 0; j < length2; j++)
                    if(s1.charAt(i+j) != s2.charAt(j))
                        break;
                if(j == length2)
                    return i;
            }
//            hashSet.add()
            if(i==length1-length2) return -1;
            val1 = ((val1-s1.charAt(i))*system + s1.charAt(i+length2))%priNumber;
            if(val1<0) val1 += priNumber;
        }
        return -1;
    }
    public int repeatSubString(String s,int subLength, int system, int priNumber){
        int length = s.length();
        int h = 1;
        int key = 0;
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < subLength-1; i++) {
            h = (h*system)%priNumber;
        }
        for (int i = 0; i < subLength; i++) {
            key = (system*key+s.charAt(i))%priNumber;
        }
        for (int i = 0; i <= length-subLength; i++) {
            if(hashMap.get(key)!=null){
                int j;
                for(j = 0; j < subLength; j++)
                    if(s.substring(hashMap.get(key), hashMap.get(key) + subLength).equals(s.substring(i, i + subLength)))
                    return i;
            }
            if(i==length-subLength) return -1;
            key = ((key-s.charAt(i))*system + s.charAt(i+subLength))%priNumber;
            if(key<0) key += priNumber;
            hashMap.put(key,i);
        }


        return -1;

    }
}
